package com.cx.algrithm.sort;

import lombok.extern.slf4j.Slf4j;

/**
 * @author shkstart
 * @date 7/23/2019 - 3:16 PM
 */
@Slf4j
public class ShellSort {
    public static void main(String[] args) {
//        显示排序前的数组
        int[] array = {1, 3, 11, -2, 2, 100, 32, 15, 52, 81};
        shellSort(array);
        for (int v : array) {
            System.out.println(v);
        }
    }

    public static int[] shellSort(int[] array) {
//        获取数值的长度
        int N = array.length;
//        第一个循环决定比较的间隔
        for (int i = N / 2; i > 0; i = i / 2) {
//            第二个循环根据间隔，将整个数组分为若干个子数组
            for (int j = i; j < N; j++) {
//                第三个循环，在子数组内部进行插入排序
                for (int k = j; k >= i && array[k] < array[k - i]; k = k - i) {
                    int temp = array[k];
                    array[k] = array[k - i];
                    array[k - i] = temp;
                }
            }
        }
        return array;
    }

    public static int[] shellSort2(int[] array) {
//        获取数值的长度
        int N = array.length;
//        第一个循环决定比较的间隔
        for (int i = N / 2; i > 0; i = i / 2) {
//            第二个循环根据间隔，将整个数组分为若干个子数组
            for (int j = i; j < N; j++) {
//                第三个循环，在子数组内部进行插入排序
                for (int k = j; k >= i && array[k] < array[k - i]; k = k - i) {
                    int temp = array[k];
                    array[k] = array[k - i];
                    array[k - i] = temp;
                }
            }
        }
        return array;
    }
}
